package com.lw.leetcode.node;

import com.lw.leetcode.linked.ListNode;

/**
 * 剑指 Offer 52. 两个链表的第一个公共节点
 * 面试题 02.07. 链表相交
 * 160. 相交链表
 *
 * @Author liw
 * @Date 2021/4/15 16:10
 * @Version 1.0
 */
public class IntersectionNode {

    public static void main(String[] args) {
        ListNode headA = new ListNode(4);
        ListNode headB = new ListNode(5);
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(8);
        ListNode c = new ListNode(4);
        ListNode d = new ListNode(5);

        ListNode e = new ListNode(0);
        ListNode f = new ListNode(1);
        headA.next = a;
        a.next = b;
        b.next = c;
        c.next = d;
        headB.next = e;
        e.next = f;
        f.next = b;

        ListNode intersectionNode = new IntersectionNode().getIntersectionNode(headA, headB);
        System.out.println(intersectionNode);
    }


    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {


        if (headA == null || headB == null) {
            return null;
        }


        int a = 0;
        ListNode l1 = headA;
        while (l1 != null) {
            a++;
            l1 = l1.next;
        }

        int b = 0;
        l1 = headB;
        while (l1 != null) {
            b++;
            l1 = l1.next;
        }

        if (a > b) {
            for (int i = 0; i < a - b; i++) {
                headA = headA.next;
            }
        }
        if (a < b) {
            for (int i = 0; i < b - a; i++) {
                headB = headB.next;
            }
        }

        a = Math.min(a, b);

        boolean flag = false;
        for (int i = 0; i < a; i++) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }


}
